This application relates to the field of computer network performance and more particularly to estimating data delays that packets encounter as they are routed through a network.
As IP networks move toward improving quality of service, Internet service providers (ISP) have been including quality of service into their service level agreements with customers. The quality of service in service level agreements may include network availability and reachability. ISPs may also include end-to-end delay benchmarks within their network into service level agreements. Such benchmarks may allow ISPs to provide better services to existing applications, such as Web browsing, as well as to new emerging services such as IP telephony and e-commerce, by providing guarantees of achieving such benchmarks.
The ability to measure quality of service may be critical to ensure that the network delivers the performance that the service level agreement promises. Measurement tools may monitor the network for compliance with the service level agreement, and identify where the provider needs to allocate more network resources.
The ability to measure quality of service may be critical to ensure that the network delivers the performance that the service level agreement promises. Measurement tools may monitor the network for compliance with the service level agreement, and identify where the provider needs to allocate more network resources.
Probe packets may be used to measure delays. Probe packets are packets that an experimenter injects into the network with the intention of measuring some aspect of their behavior, such as delay. Although probe packets could be actual user data packets, typically they are not because the experimenter wants to control the probes behavior more fully than the user""s application would permit. For example, the experimenter might wish to prescribe exactly when probes are transmitted or to set the packets sizes. The experimenter might want to make the packets as small as possible to minimize their usage of network resources. Injecting probe packets into a network involves the routine use of standard networking utilities available on any PC or workstation.
One technique for estimating benchmarks related to end-to-end data traffic delay is to send small probe packets and measure their delays. For example, the Internet utility xe2x80x9cPingxe2x80x9d measures the delays that the probe packets experience as they travel from one network location to another. One-way delay measurements require the clocks at the two endpoints to be synchronized, but round trip delay measurements require only that the router at the destination reflect probe packets back to the source. Many ISPs use probes to measure delay performance within their networks. Some commercial companies use probes to measure and compare different ISP network performance.
To determine what probes really measure, account may have to be made for the fact that probes and data may xe2x80x9cseexe2x80x9d different delay distributions because they arrive differently to a queuing system. Data traffic might be bursty, causing a later arrival to xe2x80x9csee,xe2x80x9d and be delayed by, an earlier data packet. Probes may see the effects of data traffic burstiness differently.
To determine how well probes measure delays, account may have to be made for sampling error, which arises since only finitely many probes in a given time interval are obtained.
By sampling from various distributions, ensemble averages of various quantities of interest such as average delay time, may be obtained. As is common in ergodic theory, conditions may be examined under which these ensemble averages are approximated by time averages. For example, Ping samples periodically (one probe every x seconds). But it may be difficult to estimate how accurately periodic sampling approximates the time average.
Even if these time averages could be accurately estimated by ensemble averaging, there remains the question of how to relate these averages obtained by using probe packets to averages involving data packets. In the prior art, practitioners may erroneously assume that the delays obtained by using probe packets are the same delays that would be experienced by data packets once sampling error is accounted for. Because obtaining probe information may be easier than obtaining data information, there is motivation to invent a method and system to convert information about probe packet delays into data delays.
The aforementioned problems may be addressed by correctly translating probe delays into data packet delays. For this purpose, a time average may be used as an intermediate quantity to pass from probe delays to data delays. Two parts may be considered. 1) Probe packets are transmitted according to the departure statistics governing a Poisson process; as described in more detail in the Detailed Description below, the user is able to estimate the time average from the probe delays with a prescribed accuracy. 2) The time average may then be related to the data packet delays. The second part is independent of the method used to obtain the time average. Thus, part 1) provides an improved estimate if the time average of the latter is of interest in another application and part 2) translates between time averages and data delays if techniques other than those in part 1) are used to estimate the time average. As an example of part 1), a better estimate of a time average, such as the fraction of time a resource is busy, may be obtained using Poisson sampling instead of periodic sampling. On the other hand, if periodic sampling were used to estimate a time average delay, the methods under 2) could still translate the time average estimate into data delay estimates.
More specifically, a method of estimating data delays in transmitting data packets from a first location to a second location on a computer network is presented including identifying a bottleneck link in a path connecting the first location to the second location; determining a queuing delay of probes at the bottleneck link by injecting probe packets at the first location; and estimating a queuing delay of data from the queuing delay of probes at the bottleneck limit.
The method of estimating data delays may further include adding a sum of data service times and a propagation delay to the queuing delay to obtain an estimate of the data delays. Determining a queuing delay of probes at the bottleneck link by injecting probe packets at the first location may include subtracting a sum of probe service times and a propagation delay from first location to second location probe delays.
Determining a queuing delay of probes at the bottleneck link by injecting probe packets at the first location may include injecting probe packets according to a probability distribution, which may include a Poisson distribution.
The method may further include determining a data packet length distribution served by the bottleneck link.
A method of estimating data delays in transmitting data packets from a first location to a second location on a computer network is also provided. The method includes transmitting probe packets on the computer network; determining probe delays for the probe packets to travel from the first location to the second location; estimating a time average from the probe delays with a prescribed accuracy; and relating the time average to the data delays.
Transmitting probe packets on the computer network may include transmitting probe packets on the computer network from the first location to the second location. Transmitting probe packets on the computer network from the first location to the second location may include transmitting probe packets on the computer network from the first location to the second location according to departure statistics consistent with a stochastic process.
Transmitting probe packets on the computer network from the first location to the second location includes transmitting probe packets on the computer network from the first location to the second location according to departure statistics consistent with a Poisson process.
A system is also provided for estimating data delays in transmitting data packets from a first location to a second location on a computer network including a computer; instructions for the computer for identifying a bottleneck link in a path connecting the first location to the second location; instructions for the computer for determining a queuing delay of probes at the bottleneck link by injecting probe packets at the first location; and instructions for the computer for estimating a queuing delay of data from the queuing delay of probes at the bottleneck limit.
The system may further include instructions for the computer for adding a sum of data service times and a propagation delay to the queuing delay to obtain an estimate of the data delays.
Instructions for determining a queuing delay of probes at the bottleneck link by injecting probe packets at the first location may include instructions for subtracting a sum of probe service times and a propagation delay from first location to second location probe delays. Instructions for determining a queuing delay of probes at the bottleneck link by injecting probe packets at the first location may include instructions for injecting probe packets according to a probability distribution, which includes a Poisson distribution. The system may further include instructions for determining a data packet length distribution served by the bottleneck link.
A system is provided for estimating data delays in transmitting data packets from a first location to a second location on a computer network. The system includes a computer; instructions for the computer for transmitting probe packets on the computer network according to departure statistics consistent with a stochastic process; instructions for the computer for determining probe delays for the probe packets to travel from the first location to the second location; instructions for the computer for estimating a time average from the probe delays with a prescribed accuracy; and instructions for the computer for relating the time average to the data delays. The stochastic process may include a Poisson process.
Also provided is a method of approximating a time average of a time-dependent variable, V, the variable representing a virtual delay of a packet upon arrival at a network link at a time t, including sending N probe packets to the data link; recording a time of arrival, Ak, where kxe2x89xa6N, of each of the N probe packets at the data link; calculating a sum of V(Ak), from k=1 to kmax, where kmax, and only kmax of the N probe packets arrive at the data link before or at the time t; calculating an expectation value of a number of packets to arrive at the data link; calculating an estimator, Z(t), given by the quotient of the sum and the expectation value of a number of packets; and approximating the time average by the estimator by bounding a variance of a difference between the estimator and the time average, the variance given by an expectation value of a time average of V(t)2 divided by the expectation value of a number of packets.
Also presented below is a method of approximating a time average of a time-dependent variable V, the time average given by             1      t        ⁢                  ∫        0        t            ⁢                        V          ⁢                      (            s            )                          ⁢                  xe2x80x83                ⁢                  ⅆ          t                      ,
where V represents a virtual delay of a packet upon arrival at a network link at the time t, including sending N probe packets to the data link so that a first of the N probe packets arrives at time Al, a second at time A2, a third at time A3 , . . . , and an Nth at time AN, where the times A1xe2x89xa6A2xe2x89xa6A3xe2x89xa6 . . . xe2x89xa6AN are consistent with a Poisson process of rate xcexp; calculating an estimator Z(t), given by       Z    ⁢          (      t      )        =            1                        λ          p                ⁢        t              ⁢                  ∑                  k          =          1                          k          max                    ⁢              xe2x80x83            ⁢              V        ⁢                  (                      A            k                    )                    
where kmax=max{k|Akxe2x89xa6t}; and approximating the time average by Z(t) by bounding a variance of a difference between Z(t) and the time average, the variance given by an expectation value of       t          -      1        ⁢            ∫      0      t        ⁢                            "AutoLeftMatch"                      V            ⁢                          (              s              )                                "AutoRightMatch"                2            ⁢              xe2x80x83            ⁢                        ⅆ          s                ÷                              (                                          λ                p                            ⁢              t                        )                    .                    
For a variable I(V(t) greater than x) that depends on a time t and a parameter x, a method is also presented below of approximating a time average of the variable I(V(t) greater than x), the variable I(V(t) greater than x) equal to unity if V(t), a virtual delay of a packet upon arrival at a network link at a time t, is greater than the parameter x, and equal to zero otherwise, including sending N probe packets to the data link; recording a time of arrival, Ak, where 1xe2x89xa6kxe2x89xa6N, of each of the N probe packets at the data link; calculating a sum of I(Ak greater than x), from k=1 to kmax, where kmax, and only kmax, of the N probe packets arrive at the data link before or at the time t, and I(Ak greater than x) is equal to unity if Ak is greater than the parameter x, and equal to zero otherwise; calculating an expectation value of a number of packets to arrive at the data link; calculating an estimator, Z(t), given by the quotient of the sum and the expectation value of a number of packets; and approximating the time average by the estimator by bounding a variance of a difference between the estimator and the time average, the variance given by an expectation value of a time average of I(V(t) greater than x)2 divided by the expectation value of a number of packets.
A method is also presented below of approximating a time average of a variable I(V(t) greater than x) that depends on a time t and a parameter x, the time average given by             1      t        ⁢                  ∫        0        t            ⁢                        I          ⁢                      (                                          V                ⁢                                  (                  t                  )                                             greater than               x                        )                          ⁢                  xe2x80x83                ⁢                  ⅆ          t                      ,
where the variable I(V(t) greater than x) is equal to unity if V(t), a virtual delay of a packet upon arrival at a network link at a time t, is greater than x, and equal to zero otherwise, including sending N probe packets to the data link so that a first of the N probe packets arrives at time A1, a second at time A2, a third at time A3, . . . , and an Nth at time AN, where the times A1xe2x89xa6A2xe2x89xa6A3xe2x89xa6 . . . xe2x89xa6AN are consistent with a Poisson process of rate xcexp; calculating an estimator Z(t), given by       Z    ⁢          (      t      )        =            1                        λ          p                ⁢        t              ⁢                  ∑                  k          =          1                          k          max                    ⁢              xe2x80x83            ⁢              I        ⁢                  (                                    A              k                         greater than             x                    )                    
where kmax=max{k|Akxe2x89xa6t} and I(Ak greater than x) is equal to unity if Ak is greater than the parameter x, and equal to zero otherwise; and approximating the time average by Z(t) by bounding a variance of a difference between Z(t) and the time average, the variance given by an expectation value of       t          -      1        ⁢            ∫      0      t        ⁢                            "AutoLeftMatch"                      I            ⁢                          (                                                V                  ⁢                                      (                    s                    )                                                   greater than                 x                            )                                "AutoRightMatch"                2            ⁢              xe2x80x83            ⁢                        ⅆ          s                ÷                  (                                    λ              p                        ⁢            t                    )                    
A method is also presented below of approximating an expectation value, E(Wd), of a delay experienced by a data packet arriving at a network link, including computing a time average of a time-dependent variable, V(t), the variable representing a virtual delay of a packet upon arrival at the network link at a time t, where the time average is given by             1      t        ⁢                  ∫        0        t            ⁢                        V          ⁢                      (            s            )                          ⁢                  xe2x80x83                ⁢                  ⅆ          s                      ;
computing an expectation value, E(U), of a packet size; computing an expectation value, E(U2), of a square of the packet size, utilizing the time average, the expectation value of a packet size, the expectation value of a square of the packet size, and a server utilization, xcfx81, to approximate the expectation value of a delay.
Utilizing the time average, the expectation value of a packet size, the expectation value of a square of the packet size, and a server utilization, xcfx81, may include utilizing the time average, the expectation value of a packet size, the expectation value of a square of the packet size, and a server utilization, xcfx81, to approximate the expectation value of a delay according to       E    ⁡          (              W        d            )        ≈                    1        ρ            ⁢              1        t            ⁢                        ∫          0          t                ⁢                              V            ⁢                          (              s              )                                ⁢                      xe2x80x83                    ⁢                      ⅆ            s                                -                            E          ⁢                      (                          U              2                        )                                    2          ⁢                      E            ⁢                          (              U              )                                          .      
A method is also presented below of approximating an expectation value, E(I(Wd greater than x)), of a variable I(Wd greater than x) that depends on a parameter x, the variable I(Wd greater than x) equal to unity if a delay of a data packet upon arrival at a network link is greater than x, and equal to zero otherwise, including computing a time average of a variable I(V(t) greater than x), the variable I(V(t) greater than x) equal to unity if V(t), a virtual delay of a packet upon arrival at the network link at a time t, is greater than the parameter x, and equal to zero otherwise.
The last method may further include approximating the expectation value according to       E    ⁢          (              I        ⁢                  (                                    W              d                         greater than             x                    )                    )        ≈            1              ρ        ⁢                  xe2x80x83                ⁢        t              ⁢                  ∫        0        t            ⁢                        I          ⁡                      (                                          V                ⁢                                  (                  s                  )                                             greater than               x                        )                          ⁢                  xe2x80x83                ⁢                              ⅆ            s                    .                    
A method is also presented below of estimating data delays in transmitting data packets from a first location to a second location on a computer network including identifying a bottleneck link in a path connecting the first location to the second location; estimating a queuing delay of data from a queuing delay of probes at the bottleneck limit; and adding a sum of data service times and a propagation delay to the queuing delay to obtain an estimate of the data delays.
A system is also presented below for estimating data delays in transmitting data packets from a first location to a second location on a computer network including a computer; instructions for the computer for identifying a bottleneck link in a path connecting the first location to the second location; instructions for the computer for estimating a queuing delay of data from a queuing delay of probes at the bottleneck limit; and instructions for the computer for adding a sum of data service times and a propagation delay to the queuing delay to obtain an estimate of the data delays.
The system may further include instructions for determining a data packet length distribution served by the bottleneck link.